package com.xk._02算法篇._08dynamicProgramming;

/**
 * @description: 找零钱
 * @author: xu
 * @date: 2022/10/18 20:20
 */
public class CoinChange {
    public static void main(String[] args) {
        //System.out.println(new CoinChange().coins4(41));
        System.out.println(new CoinChange().coins5(0, new int[]{1}));
    }

    // 通用实现
    public int coins5(int money, int[] faces) {
        if (money < 0 || faces == null || faces.length == 0) return -1;
        // dp[i] 表示凑够 i 分时，最小的硬币个数
        int[] dp = new int[money + 1];
        for (int i = 1; i <= money; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face) continue;
                int value = dp[i - face];
                if (value < 0 || value >= min) continue;
                min = value;
            }
            if (min == Integer.MAX_VALUE) dp[i] = -1;
            else dp[i] = min + 1;
        }
        return dp[money];
    }

    // 递推 自底向上
    public int coins4(int money){
        if (money < 1) return -1;
        int[] dp = new int[money + 1];
        int[] faces = new int[]{1, 5, 20, 25};
        // ints[i] 表示凑够 i 分时最后选择的那枚硬币的面值
        int[] ints = new int[dp.length];
        for (int i = 1; i <= money; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i >= face && dp[i - face] < min) {
                    min = dp[i - face];
                    ints[i] = face;
                }
            }
            dp[i] = min + 1;
            print(ints, i);
        }
        //print(ints, money);
        return dp[money];
    }
    private void print(int[] ints, int money) {
        System.out.print("[" + money + "] = ");
        while (money > 0) {
            System.out.print(ints[money] + " ");
            money -= ints[money];
        }
        System.out.println();
    }

    // 递推 自底向上
    static int coins3(int money) {
        if (money < 1) return -1;
        int[] dp = new int[money + 1];
        for (int i = 1; i <= money; i++) {
            int min = dp[i - 1];
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[money];
    }

    //记忆化搜索 自顶向下的调用
    public int coins2(int money) {
        if (money < 1) return -1;
        int[] dp = new int[money + 1];
        int[] faces = new int[]{1, 5, 20, 25};
        for (int face : faces) {
            if (money < face) break;
            dp[face] = 1;
        }
        return coins2(money, dp);
    }
    private int coins2(int money, int[] dp) {
        if (money < 1) return Integer.MAX_VALUE;
        if (dp[money] == 0) {
            int min1 = Math.min(coins2(money - 25, dp), coins2(money - 20, dp));
            int min2 = Math.min(coins2(money - 5, dp), coins2(money - 1, dp));
            dp[money] = Math.min(min1, min2) + 1;
        }
        return dp[money];
    }

    // 暴力递归 自顶向下的调用，出现了重叠子问题
    public int coins1(int money) {
        if (money < 1) return Integer.MAX_VALUE;
        if (money == 25 || money == 20 || money == 5 || money == 1) return 1;
        int min1 = Math.min(coins1(money - 25), coins1(money - 20));
        int min2 = Math.min(coins1(money - 5), coins1(money - 1));
        return Math.min(min1, min2) + 1;
    }
}
